Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 94/115

Q: Which statement is correct of suffix tree with a string of length n?
A. The tree has n leaves.
B. The tree has n roots
C. Height of Tree is n
D. Depth of tree is n
Solution: In computer science, a suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. For a string of length n, the suffix tree has leaves equal to n.
Q: Do all the nodes have at least two children in suffix tree.
A. True
B. False
C. ...
D. ...
Solution: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. All the nodes (internal) except for the root nodes have at least two children.
Q: Can the two edges that are coming out of a node have labels of string beginning with the same character?
A. True
B. False
C. ...
D. ...
Solution:  It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. All the nodes (internal) except for the root nodes have at least two children. No two edges that are coming out of a node have labels of string beginning with the same character.
Q: Which tree allows fast implementation of a set of string operation?
A. Rope Tree
B. Tango Tree
C. Generalized Suffix Tree
D. Top Tree
Solution: In computer science, the generalized suffix is a special suffix tree which contains a set of strings or set of words instead of a single string like suffix tree. Hence Different operation can be performed on a set of strings using a generalized suffix tree.
Q: What is a time complexity for checking a string of length n is substring or not?
A. O (log n!)
B. O (n!)
C. O (n2)
D. O (n)
Solution: Suffix tree is also known as PAT tree or position tree. It allows fast string operation. Total time taken for construction of suffix tree is linear to the length of the tree. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n).
Q: What is a time complexity for x pattern occurrence of length n?
A. O (log n!)
B. Ɵ (n!)
C. O (n2)
D. Ɵ (n + x)
Solution: Suffix tree is also known as PAT tree or position tree. It allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for x pattern occurrence of length n is Ɵ (n + x).
Q: What is a time complexity for finding the longest substring that is common in string S1 and S2 (n1 and n2 are the string lengths of strings s1, s2 respectively)?
A. O (log n!)
B. Ɵ (n!)
C. O (n2+ n1)
D. Ɵ (n1 + n2)
Solution: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest substring that is common in string S1 and S2 is Ɵ (n1 + n2).
Q: What is a time complexity for finding the longest substring that is repeated in a string?
A. O (log n!)
B. Ɵ (n!)
C. O (n2+ n1)
D. Ɵ (n)
Solution: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest substring that is repeated in a string is Ɵ (n).
Q: What is a time complexity for finding frequently occurring of a substring of minimum length in a string?
A. Ɵ (n)
B. Ɵ (n!)
C. O (n2+ n1)
D. O (log n!)
Solution: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding frequently occurring of a substring of minimum length in a string is Ɵ (n).
Q: What is a time complexity for finding the longest prefix that is common between suffix in a string?
A. Ɵ (n)
B. Ɵ (n!)
C. Ɵ (1)
D. O (log n!)
Solution: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest prefix that is common between suffix in a string is Ɵ (1).

You Have Score    /10